import node.ThreeNode;

//TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
public class Main2 {
    public static void main(String[] args) {
        //TIP Press <shortcut actionId="ShowIntentionActions"/> with your caret at the highlighted text
        // to see how IntelliJ IDEA suggests fixing it.
        System.out.printf("Hello and welcome!");

        //生成一棵N层满二叉树
        //n层满二叉树的结点总数计算公式为 (2^n - 1)
        //每一层最大数量 2^(i-1)
        double level=3;
        double count=Math.pow(2L,level)-1.0;
        ThreeNode<Integer> r1=Tree.creatCompleteBinaryTree((int) count,"a");
        ThreeNode<Integer> r2=Tree.creatCompleteBinaryTree((int) count,"b");
        ThreeNode<Integer> r3=Tree.creatCompleteBinaryTree((int) count,"c");
        ThreeNode<Integer> r4=Tree.creatCompleteBinaryTree((int) count,"d");

        r1.parent=r2;
        r2.parent=r3;
        r3.parent=r4;
        r4.parent=r1;

        ThreeNode<Integer> startNode=r1.right;
        ThreeNode<Integer> startNodeRoot=r1;
        traversalNode(startNode,null,startNodeRoot);
    }

    private static void traversalNode(ThreeNode<Integer> node,ThreeNode<Integer> curNode,ThreeNode<Integer> startRootNode){
        if (node==startRootNode && node.right!=curNode && node.left!=curNode && curNode!=null){
            return;
        }
        System.out.print(node.tag+""+node.data + " ");
        if (node.left!=null && node.left!=curNode) {
            traversalNode(node.left,node,null);
        }
        if (node.right!=null && node.right!=curNode) {
            traversalNode(node.right,node,null);
        }
        if (node.parent!=null && node.parent!=curNode) {
            traversalNode(node.parent,node,startRootNode);
        }
    }
}